# -*- encoding: utf-8 -*-


class Heap(object):
    def __init__(self):
        self.h = []
        self.size = 0

    def left_child(self, i):
        """i 为list下标，非第几个元素，返回值也是list下标"""
        if i * 2 + 1 < self.size:
            return i * 2 + 1
        return None

    def right_child(self, i):
        """i 为list下标，非第几个元素，返回值也是list下标"""
        if i * 2 + 2 < self.size:
            return i * 2 + 2
        return None

    def heapify(self, i):
        """
        i 为list下标，非第几个元素
        堆化：对i下标的元素及其子树进行堆化，使其满足完全二叉树
        """
        if i < self.size:
            m = i
            # 与子节点进行比较，如果大于父节点，则需要交换位置
            lc = self.left_child(i)
            rc = self.right_child(i)
            if lc and self.h[lc] > self.h[m]:
                m = lc
            if rc and self.h[rc] > self.h[m]:
                m = rc
            if m != i:
                self.h[m], self.h[i] = self.h[i], self.h[m]
                self.heapify(m)

    def build_heap(self, a):
        """将输入参数a序列转换成堆结构"""
        self.size = len(a)
        self.h = list(a)
        # 从下往上堆化
        for i in range(self.size // 2, -1, -1):
            self.heapify(i)

    def insert(self, data):
        """往堆中增加新元素"""
        self.h.append(data)
        current = self.size
        self.size += 1
        while self.h[current] < self.h[current // 2]:
            self.h[current], self.h[current // 2] = self.h[current // 2], self.h[current]
            current = current // 2

    def heap_sort(self):
        current_size = self.size
        while self.size > 0:
            self.h[0], self.h[self.size - 1] = self.h[self.size - 1], self.h[0]
            self.size -= 1
            self.heapify(0)
        self.size = current_size

    def display(self):
        print(self.h)


def main():
    l = list(map(int, input().split()))  # 1 4 5 7 8 13 16 19 20
    h = Heap()
    h.build_heap(l)
    h.insert(9)
    h.display()
    h.heap_sort()
    h.display()


if __name__ == '__main__':
    main()
